蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Convert Sorted List to Binary Search Tree

发表于 更新于 分类于 阅读次数： Valine：

题目大意

将一个升序链表转为有序二叉树
和上一题的不同仅仅是将数组换成了链表

解题思路

  1. 首先想到的是将链表存入数组，然后和上一题相同。
  2. 网上思路是用快慢指针，慢指针每次走一格,快指针每次走两格
    具体来说，也是找中间指针,快指针走到最后，慢指针走到中间。然后将中间数作为左边递归的最后一个数，右边则是中间开始到最后。递归下去。

    代码

    转为数组（街上一题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if len(nums) == 0:
            return None
        if len(nums) == 1:
            return TreeNode(nums[0])
        if len(nums)%2 == 1:
            tree = TreeNode(nums[len(nums)/2])
            tree.left = self.sortedArrayToBST(nums[:(len(nums)/2)])
            tree.right = self.sortedArrayToBST(nums[-(len(nums)/2):])
        else:
            tree = TreeNode(nums[len(nums)/2-1])
            tree.left = self.sortedArrayToBST(nums[:(len(nums)/2)-1])
            tree.right = self.sortedArrayToBST(nums[-(len(nums)/2):])
        return tree
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        array = []
        if head:
            while head:
                array.append(head.val)
                head = head.next
            return self.sortedArrayToBST(array)
        return []

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a list node
    # @return a tree node
    def convert(self,head,tail):
        if head==tail:
            return None
        if head.next==tail:
            return TreeNode(head.val)
        mid=head
        fast=head
        while fast!=tail and fast.next!=tail:
            fast=fast.next.next
            mid=mid.next
        node=TreeNode(mid.val)
        node.left=self.convert(head,mid)
        node.right=self.convert(mid.next,tail)
        return node
    def sortedListToBST(self, head):
        return self.convert(head,None)

第一种方法比第二种在运算速度上要快

总结

这题直接从上一题自己的代码改的，要说有什么总结直接看上一题就好了。